#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 647. 回文子串
    // https://leetcode.cn/problems/palindromic-substrings/
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        int ans = 0;
        for (int i = n-1; i>=0; --i)
        {
            for (int j = i; j<n; ++j)
            {
                if (s[i] == s[j])
                {
                    if (i==j || i+1==j) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }
                if (dp[i][j])
                    ++ans;
            }
        }
        return ans;
    }

    // 5. 最长回文子串
    // https://leetcode.cn/problems/longest-palindromic-substring/
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        int maxlen = 1;
        int index = 0;

        for (int i = n-1; i>=0; --i)
        {
            for (int j = i; j<n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
                if (dp[i][j] && j-i+1 > maxlen)
                {
                    maxlen = j-i+1;
                    index = i;
                }
            }
        }
        return s.substr(index, maxlen);
    }

    // 1745. 分割回文串 IV
    // https://leetcode.cn/problems/palindrome-partitioning-iv/
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        for (int i = n-1; i>=0; --i)
        {
            for (int j = i; j<n; ++j)
            {
                if (s[i] == s[j])
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
            }
        }

        for (int i = 1; i<n; ++i)
        {
            for (int j = i+1; j<n; ++j)
            {
                if (dp[0][i-1] && dp[i][j-1] && dp[j][n-1])
                    return true;
            }
        }
        return false;
    }
};